package com.tedu;

import java.util.Arrays;

/**
 * 插入排序：将序列分为排好序和未排序部分，遍历未排序部分的元素，对遍历的元素进行插入操作，插入到排好序部分的正确位置
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] a = new int [10];
        for (int i = 0; i <10; i++) {
            a[i]= (int) (100*Math.random());
        }
        System.out.println(Arrays.toString(a));
//        外层for循环用于对未排序部分进行遍历，i表示遍历到的元素下标
        for(int i=1;i<a.length;i++){
//            内层for循环用于对插入元素进行插入到适当位置去，j表示插入元素的实时下标
            for(int j=i;j>0&&a[j]<a[j-1];j--){
//                交换位置
                int tmp = a[j];
                a[j]= a[j-1];
                a[j-1]= tmp;
            }
        }
        System.out.println(Arrays.toString(a));
    }
}
